package Hard;
//72. 编辑距离
/*
 * 题目：
 * 给你两个单词word1和word2，请你计算出将word1转换成word2 所使用的最少操作数。
 * 你可以对一个单词进行如下三种操作：
 * ~插入一个字符
 * ~删除一个字符
 * ~替换一个字符
 * */

/*
 * 我的分析：（下面的我的思路是错误的）
 * word1和word2较长的那个字符串的length，代表最多经过length次操作，一定可以完成要求
 * i指向word1，j指向word2
 * dp[word1.length][word2.length]
 * dp[i][j] 代表 word1.substring(0,i+1) 和 word2.substring(0,j+1)中，相同元素的个数
 * 且相同元素必须按照顺序相同，如rox和ory 仅代表有1个相同元素
 * 因为r -> ory 找到了r
 *    ro -> ory 当前i指向o开始，j指向y，不再存在连续相同的元素
 *    rox -> ory
 * 因此 dp[i][j] = dp[i-1][j] + W
 * W = word2.substring(Y+1,j+1)中，是否存在一个元素M使得 M== word1.charAt(i)
 *   如果不存在，则W = 0 ， Y复原到本次判定前的初始值
 *   如果存在， 则W = 1 ，更新Y为本次判定后的位置
 * 然后定义一个结果数组result[][]
 * result[i][j]代表 截止到word1的第i个字符和word2的第j个字符，word1要变成word2的最少操作次数
 * 最少操作次数 = 两字符串取其长 - 相同元素个数
 * result[i][j] = ( 1+Max(i,j) ) - dp[i][j]
 *
 * 结论：这个思路是错误的，因为无法考虑到word1出现的字符顺序匹配word2时，可以达到最优解的情况
 *
 * */

/*
 * 正确思路：
 * 题目所给的三个操作，等价于以下三种操作：
 * 1. 在单词a中增加一个字符
 * 2. 在单词b中增加一个字符
 * 3. 修改单词a的一个字符
 * 于是有：
 * dp[i][j] = min( dp[i-1][j] , dp[i][j-1], dp[i-1][j-1]+M ) + 1; M=0(if a.i != b.j;else M=1)
 * dp[i][j] 表示word1到i位置，word2到b位置时，word1与word2的编辑距离
 * */
public class Solution72 {

    public static int minDistance(String word1, String word2) {
        int length1 = word1.length();
        int length2 = word2.length();
        int dp[][] = new int[length1 + 1][length2 + 1];
        // 注意： 下标为0的时候代表为空字符串，下标为1代表word1的第一个字符，而不是第二个字符
        dp[0][0] = 0;
        if (length1 > 0) {
            for (int i = 1; i < length1 + 1; i++) {
                dp[i][0] = i;
            }
        }
        if (length2 > 0) {
            for (int i = 1; i < length2 + 1; i++) {
                dp[0][i] = i;
            }
        }
        // dp初始化完毕
        int M;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                M = 0;
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) M = -1;
                dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1] + M);
            }
        }
        return dp[length1][length2];
    }

    public static int minDistance_error(String word1, String word2) {
        int length1 = word1.length();
        int length2 = word2.length();
        int dp[][] = new int[length1][length2];
        int result[][] = new int[length1][length2];
        int Y;
        for (int j = 0; j < length2; j++) {
            Y = -1;
            for (int i = 0; i < length1; i++) {
                if (j == 5) {
                    System.out.println("断点测试中");
                }
                if (i == 0 && j == 0) {
                    //初始化
                    if (word1.charAt(0) == word2.charAt(0))
                        dp[i][j] = 1;
                    else
                        dp[i][j] = 0;
                    continue;
                }
                char ch = word1.charAt(i);
                String sub = word2.substring(Y + 1, j + 1);
                int oldY = Y;
                int W = 0;
                // 在sub中寻找ch，如果能找到，W=1，否则，Y = oldY
                for (int k = Y + 1; k < j + 1; k++) {
                    if (ch == word2.charAt(k)) { // 注意Y初始为-1
                        W = 1;
                        Y = k;
                        break;
                    }
                }
                if (W == 0) {
                    Y = oldY;
                }
                if (i > 0) {
                    dp[i][j] = dp[i - 1][j] + W;
                } else {
                    dp[i][j] = W;
                }
            }
        }
        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++) {
                result[i][j] = 1 + Math.max(i, j) - dp[i][j];
            }
        }
        // test
        for (int j = 0; j < length1; j++) {
            for (int i = 0; i < length2; i++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("-------------");
        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++) {
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
        return result[length1 - 1][length2 - 1];
    }

    public static void main(String[] args) {
        System.out.println(minDistance("intention", "execution"));
    }
}
